package com.zyk.grate_offer.class05;

/**
 * 给定一个char[][] matrix，也就是char类型的二维数组，再给定一个字符串word，
 * 可以从任何一个某个位置出发，可以走上下左右，能不能找到word？
 * char[][] m = {  { 'a', 'b', 'z' }, 
 * { 'c', 'd', 'o' }, 
 * { 'f', 'e', 'o' }, 
 * 设定1：可以走重复路的情况下，返回能不能找到
 * 比如，word = "zoooz"，是可以找到的，z -> o -> o -> o -> z，因为允许走一条路径中已经走过的字符
 * 设定2：不可以走重复路的情况下，返回能不能找到
 * 比如，word = "zoooz"，是不可以找到的，因为允许走一条路径中已经走过的字符不能重复走 
 *
 * @author zhangsan
 * @date 2021/5/6 16:55
 */
public class Code04_LookingForString {

    // 可以走重复路
    public static boolean can1(char[][] matrix, String target) {
        if (target == null || target.equals("")) return true;
        int R = matrix.length, C = matrix[0].length;
        char[] str = target.toCharArray();
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (process(matrix, r, c, R, C, str, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean process(char[][] matrix, int r, int c, int R, int C, char[] str, int i) {
        if (i == str.length) return true;
        if (r < 0 || r == R || c < 0 || c == C) return false;
        if (matrix[r][c] != str[i]) return false;
        return process(matrix, r + 1, c, R, C, str, i + 1) ||
                process(matrix, r, c + 1, R, C, str, i + 1) ||
                process(matrix, r - 1, c, R, C, str, i + 1) ||
                process(matrix, r, c - 1, R, C, str, i + 1);
    }


    // 不可以走重复路
    public static boolean can2(char[][] matrix, String target) {
        if (target == null || target.equals("")) return true;
        int R = matrix.length, C = matrix[0].length;
        char[] str = target.toCharArray();
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (process2(matrix, r, c, R, C, str, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean process2(char[][] matrix, int r, int c, int R, int C, char[] str, int i) {
        if (i == str.length) return true;
        if (r < 0 || r == R || c < 0 || c == C) return false;
        if (matrix[r][c] != str[i]) return false;
        matrix[r][c] = '\0';
        return process2(matrix, r + 1, c, R, C, str, i + 1) ||
                process2(matrix, r, c + 1, R, C, str, i + 1) ||
                process2(matrix, r - 1, c, R, C, str, i + 1) ||
                process2(matrix, r, c - 1, R, C, str, i + 1);
    }


    // for test
    public static void main(String[] args) {
        char[][] matrix = {
                {'a', 'b', 'z'},
                {'c', 'd', 'o'},
                {'f', 'e', 'o'}
        };
        String target = "zoooz";
        System.out.println(can1(matrix, target));
        System.out.println(can2(matrix, target));
    }

}
